//
//  main.cpp
//  图 上机
//

//  Created by Yan Zihao on 2024/12/7.
//

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTICES 8

// 定义邻接矩阵
int graph[MAX_VERTICES][MAX_VERTICES];
bool visited[MAX_VERTICES];

// 初始化图
void initGraph()
{
    for (int i = 0; i < MAX_VERTICES; i++)
    {
        for (int j = 0; j < MAX_VERTICES; j++)
        {
            graph[i][j] = 0;
        }
    }
}

// 添加边（有向图）
void addEdge(int u, int v)
{
    graph[u][v] = 1; // 单向连接
}

// 深度优先搜索 (DFS)
void DFS(int vertex)
{
    visited[vertex] = true;

    // 打印当前节点
    printf("%d ", vertex + 1); // 打印节点，+1是为了符合题目节点编号

    // 遍历所有邻接节点，按从小到大的顺序递归
    for (int i = 0; i < MAX_VERTICES; i++)
    {
        // 检查图中是否存在边且该节点未被访问
        if (graph[vertex][i] == 1 && !visited[i])
        {
            DFS(i); // 递归调用DFS
        }
    }
}

// 广度优先搜索 (BFS)
void BFS(int start)
{
    bool visited[MAX_VERTICES] = {false};
    int queue[MAX_VERTICES];
    int front = 0, rear = 0;

    queue[rear++] = start;
    visited[start] = true;

    while (front < rear)
    {
        int current = queue[front++];
        printf("%d ", current + 1); // 打印当前顶点

        for (int i = 0; i < MAX_VERTICES; i++)
        {
            if (graph[current][i] == 1 && !visited[i])
            {
                queue[rear++] = i;
                visited[i] = true;
            }
        }
    }
}

int main()
{
    initGraph();

    // 构建图 (根据题目中的图)
    addEdge(0, 1); // 1 -> 2
    addEdge(0, 2); // 1 -> 3
    addEdge(1, 3); // 2 -> 4
    addEdge(3, 7); // 4 -> 8
    addEdge(4, 1); // 5 -> 2
    addEdge(4, 7); // 5 -> 8
    addEdge(2, 5); // 3 -> 6
    addEdge(2, 6); // 3 -> 7
    addEdge(5, 6); // 6 -> 7
    addEdge(6, 4);

    printf("深度优先遍历: ");
    for (int i = 0; i < MAX_VERTICES; i++)
    {
        visited[i] = false; // 重置访问标记
    }
    DFS(0); // 从节点1开始

    printf("\n广度优先遍历: ");
    BFS(0); // 从节点1开始

    printf("\n");

    return 0;
}
